"""
给定一个长度为4的整数数组 cards 。你有 4 张卡片,每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式,以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法,而不是整数除法。
例如, 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是,不能使用 “-” 作为一元运算符。
例如,如果 cards =[1,1,1,1] ,则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如,如果 cards =[1,2,1,2] ,则表达式 “12 + 12” 无效。
如果可以得到这样的表达式,其计算结果为 24 ,则返回 true ,否则返回 false 。



示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24
示例 2:

输入: cards = [1, 2, 1, 2]
输出: false


提示:

cards.length == 4
1 <= cards[i] <= 9


"""

from typing import List


class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        permutations = self.permuteUnique(nums)
        for permutation in permutations:
            if self.compute(permutation):
                return True
        return False

    # 唯一排序
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        permutations = []
        nums.sort()
        tmp = []
        visited = [False] * len(nums)
        self.backtracking(nums, tmp, visited, permutations)
        return permutations

    # 回溯
    def backtracking(self, nums: List[int], tmp: List[float], visited: List[bool], perm: List[int]) -> None:

        if len(nums) == len(tmp):
            perm.append(tmp[:])
            return
        for i in range(len(nums)):
            # 已经判断过就跳过
            if visited[i]:
                continue
            #   如果当前的和上一个相同，就跳过，同时要求没有被使用过
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue
            visited[i] = True
            tmp.append(nums[i])
            self.backtracking(nums, tmp, visited, perm)
            visited[i] = False
            tmp.pop()

    def compute(self, nums: List[float]) -> bool:
        if len(nums) == 1:
            return abs(nums[0] - 24) <= 0.00001
        # 生成 0-3 的 数字,并进行遍历
        for i in range(len(nums) - 1):  # 计算+-*/对应的结果
            # tmp 追加 第一位数字和第二位数字的加减乘除
            tmp = []
            tmp.append(nums[i] + nums[i + 1])
            tmp.append(nums[i] - nums[i + 1])
            tmp.append(nums[i] * nums[i + 1])
            if nums[i + 1] != 0:
                tmp.append(nums[i] / nums[i + 1])
            # 获取 前两位的加减乘除
            for num in tmp:
                # 把输入的数组扔进一个新的数组
                new_list = nums[:]
                # 把当前位 赋值成 前两位的结果
                new_list[i] = num
                #  弹出当前位的下一位,如 i= 0 ,弹出 new_list[1],不断迭代。直至数组剩下最后一位,计算误差
                new_list.pop(i + 1)
                if self.compute(new_list):
                    return True
        return False


if __name__ == '__main__':
    nums = [4, 1, 8, 7]
    solution = Solution()
    print(solution.judgePoint24(nums))
